package lc_1335_工作计划的最低难度;

import java.util.Arrays;

public class Solution {
	
	int inf_int = 0x3f3f3f3f;

	public int minDifficulty(int[] jobDifficulty, int d) {
		int n = jobDifficulty.length;
		int[][] dp = new int[d + 1][n + 1];
		for (int i = 0; i <= d; i++) {
			Arrays.fill(dp[i], inf_int);
		}
		dp[0][0] = 0;
		for (int i = 1; i < d + 1; i++) {
			for (int j = i; j < n + 1; j++) {
				int mx = 0;
				for (int k = j; k >= i; k--) {
					mx = Math.max(mx, jobDifficulty[k - 1]);
					dp[i][j] = Math.min(dp[i - 1][k - 1] + mx, dp[i][j]);
				}
			}
		}
		return dp[d][n] == inf_int ? -1 : dp[d][n];
	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.minDifficulty(new int[] { 6, 5, 4, 3, 2, 1 }, 2);
	}
}